package myself.a012AndCollect;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Stack;

/**
 * @author 叶之越
 * Description
 * Date 2021/1/31
 * Time 16:03
 * Mail 739153436@qq.com
 */
public class NumberOfIslands {

    // 第一种，递归解法，优秀但是不太通用
    public static int numIslands3(char[][] board) {
        if (board == null || board.length == 0) {
            return 0;
        }
        int count = 0;
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[i].length; j++) {
                if (board[i][j] == '1') {
                    count++;
                    infect(board, i, j);
                }
            }
        }
        return count;
    }

    // 从(i,j)这个位置出发，把所有练成一片的'1'字符，变成0
    public static void infect(char[][] board, int i, int j) {
        if (i < 0 || j < 0 || i >= board.length || j >= board[i].length || board[i][j] != '1') {
            return;
        }
        board[i][j] = '0';
        // 上下左右
        infect(board, i, j - 1);
        infect(board, i, j + 1);
        infect(board, i - 1, j);
        infect(board, i + 1, j);
    }

    // 第二种，并查集
    public static int numIslands1(char[][] board) {
        if (board == null || board.length == 0) return 0;
        Dot[][] dots = new Dot[board.length][board[0].length];
        List<Dot> list = new ArrayList<>();
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board.length; j++) {
                if (board[i][j] == '1') {
                    dots[i][j] = new Dot();
                }
                list.add(dots[i][j]);
            }
        }
        // 创建并查集
        UnionFind1<Dot> union = new UnionFind1<>(list);
        int row = board.length;
        int col = board[0].length;
        // 第一行遍历比较
        for (int i = 1; i < col; i++) {
            if (board[0][i - 1] == '1' && board[0][i] == '1') {
                union.union(dots[0][i - 1], dots[0][i]);
            }
        }
        // 第一列遍历比较
        for (int i = 1; i < row; i++) {
            if (board[i - 1][0] == '1' && board[i][0] == '1') {
                union.union(dots[i - 1][0], dots[i][0]);
            }
        }
        for (int i = 1; i < row; i++) {
            for (int j = 1; j < col; j++) {
                // 向上比较是否关联
                if (board[i - 1][j] == '1' && board[i][j] == '1') {
                    union.union(dots[i - 1][j], dots[i][j]);
                }
                // 向下比较是否关联
                if (board[i][j - 1] == '1' && board[i][j] == '1') {
                    union.union(dots[i][j - 1], dots[i][j]);
                }
            }
        }
        return union.sets();
    }


    // 第三种，并查集优化版本
    public static int numIslands2(char[][] board) {
        int row = board.length;
        int col = board[0].length;
        UnionFind2 uf = new UnionFind2(board);
        for (int j = 1; j < col; j++) {
            if (board[0][j - 1] == '1' && board[0][j] == '1') {
                uf.union(0, j - 1, 0, j);
            }
        }
        for (int i = 1; i < row; i++) {
            if (board[i - 1][0] == '1' && board[i][0] == '1') {
                uf.union(i - 1, 0, i, 0);
            }
        }
        for (int i = 1; i < row; i++) {
            for (int j = 1; j < col; j++) {
                if (board[i][j] == '1') {
                    if (board[i][j - 1] == '1') {
                        uf.union(i, j - 1, i, j);
                    }
                    if (board[i - 1][j] == '1') {
                        uf.union(i - 1, j, i, j);
                    }
                }
            }
        }
        return uf.sets();
    }

    // 下面是辅助的数据结构
    public static class Dot {

    }

    public static class Node<V> {

        V value;

        public Node(V v) {
            value = v;
        }

    }

    public static class UnionFind1<V> {
        public HashMap<V, Node<V>> nodes;
        public HashMap<Node<V>, Node<V>> parents;
        public HashMap<Node<V>, Integer> sizeMap;

        public UnionFind1(List<V> values) {
            nodes = new HashMap<>();
            parents = new HashMap<>();
            sizeMap = new HashMap<>();
            for (V cur : values) {
                Node<V> node = new Node<>(cur);
                nodes.put(cur, node);
                parents.put(node, node);
                sizeMap.put(node, 1);
            }
        }

        public Node<V> findFather(Node<V> cur) {
            Stack<Node<V>> path = new Stack<>();
            while (cur != parents.get(cur)) {
                path.push(cur);
                cur = parents.get(cur);
            }
            while (!path.isEmpty()) {
                parents.put(path.pop(), cur);
            }
            return cur;
        }

        public void union(V a, V b) {
            Node<V> aHead = findFather(nodes.get(a));
            Node<V> bHead = findFather(nodes.get(b));
            if (aHead != bHead) {
                int aSetSize = sizeMap.get(aHead);
                int bSetSize = sizeMap.get(bHead);
                Node<V> big = aSetSize >= bSetSize ? aHead : bHead;
                Node<V> small = big == aHead ? bHead : aHead;
                parents.put(small, big);
                sizeMap.put(big, aSetSize + bSetSize);
                sizeMap.remove(small);
            }
        }

        public int sets() {
            return sizeMap.size();
        }
    }

    public static class UnionFind2 {
        // 模拟集合链表关系的数组
        private int[] parent;
        // 代表每个集合的长度
        private int[] size;
        // 辅助数组，用于重新连接链表
        private int[] help;
        // 列数
        private int col;
        private int sets;

        public UnionFind2(char[][] board) {
            col = board[0].length;
            sets = 0;
            int row = board.length;
            int len = row * col;
            parent = new int[len];
            size = new int[len];
            help = new int[len];
            for (int r = 0; r < row; r++) {
                for (int c = 0; c < col; c++) {
                    if (board[r][c] == '1') {
                        int i = index(r, c);
                        parent[i] = i;
                        size[i] = 1;
                        sets++;
                    }
                }
            }
        }

        // (r,c) -> i
        private int index(int r, int c) {
            return r * col + c;
        }

        // 原始位置 -> 下标
        private int find(int i) {
            int hi = 0;
            while (i != parent[i]) {
                help[hi++] = i;
                i = parent[i];
            }
            for (hi--; hi >= 0; hi--) {
                parent[help[hi]] = i;
            }
            return i;
        }

        public void union(int r1, int c1, int r2, int c2) {
            int i1 = index(r1, c1);
            int i2 = index(r2, c2);
            int f1 = find(i1);
            int f2 = find(i2);
            if (f1 != f2) {
                if (size[f1] >= size[f2]) {
                    size[f1] += size[f2];
                    parent[f2] = f1;
                } else {
                    size[f2] += size[f1];
                    parent[f1] = f2;
                }
                sets--;
            }
        }

        public int sets() {
            return sets;
        }

    }
}
